1. Field of the Invention
The present invention relates to an image processing apparatus, an image processing method, and a storage medium.
2. Description of the Related Art
As a method for generating bitmap image data from a print job, Japanese Patent Application Laid-Open No. 2006-140597 discusses a scanline algorithm. FIG. 1 illustrates a concept of the scanline algorithm. In the following descriptions, a case where bitmap image data 301 is generated from a print job 300 including a rectangular graphic object 300a and a T-shaped graphic object 300b will be described.
According to the scanline algorithm, information of the object included in the print job 300 is calculated. The information contains “edge” 302, which indicates both ends of the object, “level” 303, which indicates an overlapping area, and “fill” 304, which indicates the color of the object. For example, left and right edges 302a and 302b, level 303a, and fill 304a are calculated from the rectangular graphic object 300a. The obtained values are linked to one another and stored. Similarly, left and right edges 302c and 302d, level 303b, and fill 304b are calculated from the T-shaped graphic object 300b. These values are also linked to one another and stored. To generate a bitmap image data, pixels between the left and the right edges are rendered using the “fill” pixels linked to the “edge”.
Regarding a portion where objects overlap, a bitmap image is rendered using the “fill” pixels linked to the “edge” of a higher “level”. Thus, only the pixels of the uppermost object are rendered on a frame buffer 305 in the generation of the bitmap image data. Accordingly, compared to a painter's algorithm, which renders all pixels of all objects on a frame buffer 401 illustrated in FIG. 2, bitmap image data can be generated more speedily by using the scanline algorithm.
There are various software applications which can be used to generate a print job. Some software applications issue redundant rendering instructions. For example, some software applications use a plurality of overlapping objects in forming one line. In such a case, a print job including continuously-arranged small objects will be generated.
FIG. 3 illustrates a case where one line is formed by one graphic object and a case where one line is formed by a plurality of graphic objects in a redundant manner. If one line is formed by one graphic object 500, the number of the edges is two (edges 500a and 500b). On the other hand, if one line is formed by a plurality of objects 501, 502, 503, 504, and 505, which are of the same configuration of a graphic object 506 and are arranged in a partially overlapping manner, the number of the edges increases since the objects 501 to 505 include edges (501a, 501b) to (505a, 505b), respectively.
Further, if data generated by a software application is used by a different software application, one object may be divided into a plurality of objects. In this case, a print job including continuously-arranged small objects will also be generated. FIG. 4 illustrates an example of one bitmap image divided into a plurality of bitmap images. The number of the edges of a bitmap image 600 is two (edges 600a and 600b). On the other hand, if the bitmap image 600 is divided into a plurality of images (bitmap images 601), the number of the edges (edges 602) increases according to the number into which the bitmap image 600 has been divided.
Regarding a print job including such continuously-arranged small objects, rendering objects of more than one million for one page is not uncommon. Thus, the number of the edges will be an enormous number.
If the scanline algorithm, which calculates edges and levels, is used in the generation of bitmap image data for a print job that includes large quantities of continuously-arranged small objects, the processing load of the edges and the levels will be very heavy. Such load can be reduced by introducing optimization processing that combines small objects into one object. According to the optimization processing, since the number of the edges and the levels is reduced, the processing load can also be reduced. Thus, high-speed generation processing of the bitmap image data can be realized. However, if the objects are simply combined without consideration, the load of the combining processing thereof will increase. Then, the high-speed generation processing of the bitmap image data is not realized.